package com.tianyuan.test1;
/**
 * 哈希
 * 两数之和
 *
 * @date 2025/10/19 10:05
 * 给出一个整型数组numbers和一个目标值target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
 * （注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）
 * 数据范围:2<len(numbers)≤10的5次方,-10≤number≤10的9次方,0≤target≤10的9次方
 * <p>
 * 输入：[3,2,4],6   返回值：[2,3]
 * 说明：因为 2+4=6，而2的下标为2，4的下标为3，又因为下标2<下标3，所以返回[2,3]
 * 输入：[20,70,110,150],90   返回值：[1,2]   说明：20+70=90
 */
/**
 * 两数之和
 *
 * @date 2025/10/19 10:05
 * 给出一个整型数组numbers和一个目标值target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
 * （注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）
 * 数据范围:2<len(numbers)≤10的5次方,-10≤number≤10的9次方,0≤target≤10的9次方
 *
 * 输入：[3,2,4],6   返回值：[2,3]
 * 说明：因为 2+4=6，而2的下标为2，4的下标为3，又因为下标2<下标3，所以返回[2,3]
 * 输入：[20,70,110,150],90   返回值：[1,2]   说明：20+70=90
 */

import java.util.*;

public class Solution {
    /**
     * 两数之和：用哈希表快速找到和为target的两个元素的1-based索引
     * @param numbers 输入的整数数组
     * @param target 目标和值
     * @return 长度为2的数组，存储两个元素的1-based索引（前小后大）
     */
    public int[] twoSum(int[] numbers, int target) {
        // 1. 初始化哈希表：key存数组元素值，value存该元素在原数组中的0-based索引
        // 作用：快速查询“目标差值”是否已出现过（避免暴力遍历的O(n²)复杂度）
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        // 2. 遍历原数组，每遍历一个元素就做两件事：检查差值、存储当前元素
        for (int i = 0; i < numbers.length; i++) {
            // 计算“目标差值”：要找到的另一个元素 = target - 当前元素
            int needNum = target - numbers[i];
            // 3. 检查哈希表中是否存在这个“目标差值”：
            // 若存在 → 说明之前遍历过的元素里有需要的数，直接返回两个索引（转1-based）
            if (map.containsKey(needNum)) {
                // map.get(needNum)：目标差值的0-based索引 → +1转1-based
                // i：当前元素的0-based索引 → +1转1-based
                // 顺序保证：先存的元素索引一定小于当前i，所以前小后大
                return new int[]{map.get(needNum) + 1, i + 1};
            }
            // 4. 若不存在 → 将当前元素和它的索引存入哈希表，供后续元素检查
            else {
                map.put(numbers[i], i);
            }
        }
        // 5. 若遍历结束仍未找到（题目默认有解，此句仅处理极端无解答情况）
        throw new IllegalArgumentException("no solution");
    }









    public static void main(String[] args) {
        Solution sol = new Solution();

        // 测试用例1：[3,2,4] 目标6
        int[] nums1 = {3, 2, 4};
        System.out.println(Arrays.toString(sol.twoSum(nums1, 6))); // 输出 [2,3]

        // 测试用例2：[20,70,110,150] 目标90
        int[] nums2 = {20, 70, 110, 150};
        System.out.println(Arrays.toString(sol.twoSum(nums2, 90))); // 输出 [1,2]

        int[] nums3 = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
        System.out.println(Arrays.toString(sol.twoSum(nums3, 17)));
    }
}
